import com.sun.javafx.fxml.LoadListener;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2023-01-08
 * Time: 21:37
 */
//Day1 - Day10
class Data{
    char c;
    int n;
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class WinterWork1 {
    //Day1
    //1.
    public static boolean Automorphic(int m){
        int ret = m * m;
        while (m > 0){
            if ((m % 10) != (ret % 10)){
                return false;
            }
            m /= 10;
            ret /= 10;
        }
        return true;
    }
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int sum = 0;
        for (int i = 0; i <= n; i++) {
            if (Automorphic(i)){
                sum++;
            }
        }
        System.out.println(sum);
    }
    //2.
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        boolean[] times = new boolean[n + 1];
        int count = 0;
        for (int i = 0; i < n; i++) {
            times[i] = true;
        }
        for (int i = 2; i <= n; i++) {
            if (times[i]){
                count++;
                for (int j = i * i; j <= n; j += i){
                    times[j] = false;
                }
            }
        }
        System.out.println(count);
    }

    //Day2
    //1.
    public int FirstNotRepeatingChar(String str) {
        char[] s = str.toCharArray();
        int[] ret = new int[57];
        for (int i = 0; i < s.length; i++) {
            ret[s[i] - 65]++;
        }
        for (int i = 0; i < s.length; i++) {
            if (ret[s[i] - 65] == 1){
                return i;
            }
        }
        return -1;
    }
    //2.
    public boolean isUnique(String astr) {
        char[] s = astr.toCharArray();
        int[] ret = new int[26];
        for (int i = 0; i < s.length; i++) {
            ret[s[i] - 65]++;
        }
        for (int i = 0; i < ret.length; i++) {
            if (ret[i] > 1){
                return false;
            }
        }
        return true;
    }

    //Day3
    //1.
    public boolean CheckPermutation(String s1, String s2) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();

        if (c1.length != c2.length){
            return false;
        }
        int[] a1 = new int[26];
        int[] a2 = new int[26];
        for (int i = 0; i < c1.length; i++) {
            a1[c1[i] - 97]++;
        }
        for (int i = 0; i < c2.length; i++) {
            a2[c2[i] - 97]++;
        }
        for (int i = 0; i < a1.length; i++) {
            if (a1[i] != a2[i]){
                return false;
            }
        }
        return true;
    }
    //2.
    public boolean canPermutePalindrome(String s) {
            char[] c = s.toCharArray();
            Arrays.sort(c);

            int i = 0, j = 1;
            int n = 0;
            while (i < c.length && j < c.length && n <= 1){
                if (c[i] != c[j]){
                    i += 2;
                    n++;
                    if (i >= c.length || c[i] != c[j]){
                        return false;
                    }
                }
                i += 2;
                j += 2;
            }
            if (j < c.length){
                return false;
            }
            return true;
    }

    //Day4
    //1.
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n != 0){
            String str = scanner.nextLine();
            if (str.length() >= 10){
                StringBuilder sb = new StringBuilder();
                sb.append(str.charAt(0));
                sb.append(str.length() - 2);
                sb.append(str.charAt(str.length() -1));
                str = sb.toString();
            }
            System.out.println(str);
        }
    }
    //2.
    public String replaceSpaces(String s, int length) {
        char[] c = s.toCharArray();

        StringBuilder sb = new StringBuilder(s.length());
        for (int i = 0; i < c.length; i++) {
            if (c[i] == ' '){
                sb.append("%20");
            }else{
                sb.append(c[i]);
            }
        }
        return sb.toString();
    }

    //Day5
    //1.
    public String compressString(String s) {
        char[] rc = s.toCharArray();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < rc.length; i++) {
            int n = 1;
            while (i < rc.length - 1 && rc[i] == rc[i + 1]){
                n++;
                i++;
            }
            sb.append(rc[i]);
            sb.append(n);
        }
        if (sb.length() >= rc.length){
            return s;
        }
        return sb.toString();
    }
    //2.
    public int exchangeBits(int num) {
        return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1);
    }

    //Day6
    //1.
    public int multiply(int A, int B) {
        if (B == 0){
            return 0;
        }
        return A + multiply(A, B - 1);
    }
    //2.
    public static void main4(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 7 == 0){
                sum++;
                continue;
            }
            int ret = i;
            while (ret > 0){
                if (ret % 10 == 7){
                    sum++;
                    break;
                }
                ret /= 10;
            }
        }
        System.out.println(sum);
    }

    //Day7
    //1.
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0){
            n /= 5;
            count += n;
        }
        return count;
    }
    //2.
    public static void main5(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double n = scanner.nextDouble();
        int m = (int)n;
        if (n - m > 0.5){
            System.out.println(m + 1);
        }else{
            System.out.println(m);
        }
    }

    //Day8
    //1.
    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[100000];
        array[0] = 1;
        array[1] = 2;
        for (int i = 2; i < 100000; i++) {
            array[i] = (2 * array[i - 1] + array[i - 2]) % 32767;
        }
        while (n > 0){
            int k = scanner.nextInt();
            System.out.println(array[k]);
            n--;
        }
    }
    //2.
    public static void main7(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        char[] c = str.toCharArray();

        int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] >= 'a' && c[i] <= 'z' || c[i] >= 'A' && c[i] <= 'Z'){
                s1++;
            }else if (c[i] == ' '){
                s2++;
            }else if (c[i] >= '0' && c[i] <= 9) {
                s3++;
            }else {
                s4++;
            }
            System.out.println(s1);
            System.out.println(s2);
            System.out.println(s3);
            System.out.println(s4);
        }
    }

    //Day9
    //1.
    public int[] runningSum(int[] nums) {
        int[] ret = new int[nums.length];
        ret[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ret[i] = ret[i - 1] + nums[i];
        }
        return ret;
    }
    //2.
    class Solution {
        public int searchInsert(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int mid = (right - left) / 2 + left;
            while (left <= right){
                if (nums[mid] > target){
                    right = mid - 1;
                }else if (nums[mid] < target){
                    left = mid + 1;
                }else{
                    break;
                }
                mid = (right - left) / 2 + left;
            }
            return mid;
        }
    }

    //Day10
    //1.
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = (right - left)  / 2 + left;

            if (nums[mid] == target){
                return mid;
            }else if(nums[mid] < nums[right]){
                if (nums[mid] < target && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }else{
                if (nums[left] <= target && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
    //2.
    public int getDecimalValue(ListNode head) {
        ListNode cur = head;
        int sum = 0;
        while (cur != null){
            sum = sum * 2 + cur.val;
            cur = cur.next;
        }
        return sum;
    }

    //Day11
    //1.
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //加个表头
        ListNode res = new ListNode(-1);
        res.next = head;
        //前序节点
        ListNode pre = res;
        //当前节点
        ListNode cur = head;
        //找到m
        for(int i = 1; i < m; i++){
            pre = cur;
            cur = cur.next;
        }
        //从m反转到n
        for(int i = m; i < n; i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        //返回去掉表头
        return res.next;
    }
    //2.
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;

        Map<Integer, ListNode> map = new HashMap<>();
        int sum = 0;
        ListNode cur = newHead;
        while (cur != null){
            sum += cur.val;
            map.put(sum, cur);
            cur = cur.next;
        }

        sum = 0;
        cur = newHead;
        while (cur != null){
            sum += cur.val;
            cur.next = map.get(sum).next;
            cur = cur.next;
        }
        return newHead.next;
    }

    //Day12
    //1.
    public void connect(ListNode cur, ListNode l, int ret){
        int flag = 0;
        while (l != null){
            int sum = l.val + ret;
            ListNode node = new ListNode(sum % 10);
            ret = 0;
            if (sum >= 10){
                ret = sum / 10;
            }
            cur.next = node;
            cur = node;
            l = l.next;
            flag = 1;
        }
        if (flag == 1 && ret > 0){
            ListNode node = new ListNode(ret);
            cur.next = node;
        }
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int ret = 0;
        ListNode l3 = new ListNode(0);
        ListNode cur = l3;


        while (l1 != null && l2 != null){
            int sum = l1.val + l2.val + ret;
            ListNode node = new ListNode(sum % 10);
            ret = 0;
            if (sum >= 10){
                ret = sum / 10;
            }
            cur.next = node;
            cur = node;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 == null && l2 == null && ret > 0){
            ListNode node = new ListNode(ret);
            cur.next = node;
        }
        connect(cur, l1, ret);
        connect(cur, l2, ret);
        return l3.next;
    }
    //2.
    public int maxDepth(String s) {
        char[] c = s.toCharArray();

        int size = 0;
        int max = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '(') size++;
            if (size > max){
                max = size;
            }
            if (c[i] == ')') size--;
        }
        return max;
    }

    //Day13
    //1.
    public String makeGood(String S) {
        char[] s = S.toCharArray();
        int top = -1;
        for (int i = 0; i < s.length; i++) {
            if (s[i] >= 'a' && s[i] <= 'z'){
                if (top == -1 || s[top] != s[i] - 32){
                    s[++top] = s[i];
                }else{
                    top--;
                }
            }else{
                if (top == -1 || s[top] != s[i] + 32){
                    s[++top] = s[i];
                }else{
                    top--;
                }
            }
        }
        return String.valueOf(s, 0, top + 1);
    }
    //2.
    Set<TreeNode> set = new HashSet<>();
    public TreeNode num(TreeNode root){
        if (root == null){
            return null;
        }
        num(root.left);
        set.add(root);
        num(root.right);

        return root;
    }
    public int numColor(TreeNode root) {
        num(root);
        return set.size();
    }

    //Day14
    //1.
    public int sumRootToLeaf(TreeNode root) {
        return sum(root, 0);
    }
    public int sum(TreeNode root, int sum){
        if (root == null){
            return 0;
        }
        sum = 2 * sum + root.val;
        if (root.left == null && root.right == null){
            return sum;
        }
        return sum(root.left, sum) + sum (root.right, sum);
    }
    //2.
    int cnt = 0;
    public int cal(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftsum = cal(root.left);
        int rightsum = cal(root.right);

        cnt += Math.abs(leftsum - rightsum);
        return leftsum + rightsum + root.val;
    }
    public int findTilt(TreeNode root) {
        cal(root);
        return cnt;
    }

    //Day15
    //1.
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();

        int height = 0;
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            TreeNode[] ret = new TreeNode[size];
            int j = 0;
            while (size != 0) {
                TreeNode cur = queue.poll();
                ret[j++] = cur;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            if (height % 2 == 0){
                if (ret[0].val % 2 == 0){
                    return false;
                }
            }else{
                if (ret[0].val % 2 != 0){
                    return false;
                }
            }
            for (int i = 1; i < ret.length; i++) {
                if (height % 2 == 0) {
                    if (ret[i - 1].val % 2 != 0 && ret[i].val % 2 != 0) {
                        if (ret[i - 1].val < ret[i].val){
                            continue;
                        }else{
                            return false;
                        }
                    }else{
                        return false;
                    }
                }else{
                    if (ret[i - 1].val % 2 == 0 && ret[i].val % 2 == 0) {
                        if (ret[i - 1].val > ret[i].val){
                            continue;
                        }else{
                            return false;
                        }
                    }else{
                        return false;
                    }
                }
            }
            height++;
        }
        return true;
    }
    //2.
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] arr3 = new int[arr1.length];
        int k = 0;

        for (int i = 0; i < arr2.length; i++) {
            for (int j = 0; j < arr1.length; j++) {
                if (arr2[i] == arr1[i]){
                    arr3[k++] = arr2[i];
                    arr1[i] = -1;
                }
            }
        }
        Arrays.sort(arr1);
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != -1){
                arr3[k++] = arr1[i];
            }
        }
        return arr3;
    }

    //Day16
    //1.
    public static String sortSentence(String s) {
        StringBuilder sb1 = new StringBuilder();

        char[] cs = s.toCharArray();
        StringBuilder sb2 = new StringBuilder();
        StringBuilder[] sb2s = new StringBuilder[9];
        int j = 0;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] >= '1' && cs[i] <= '9'){
                sb2s[cs[i] - '0' - 1] = sb2;
                sb2s[cs[i] - '0' - 1].append(' ');
                sb2 = new StringBuilder();
                i++;
                continue;
            }
            sb2.append(cs[i]);
        }
        for (int i = 0; i < sb2s.length; i++) {
            if (sb2s[i] != null){
                sb1.append(sb2s[i]);
            }
        }
        return sb1.toString();
    }
    //2.
    public int findLHS(int[] nums) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int ret = 0;

        for (int num: nums){
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }

        for (int key: hashMap.keySet()){
            if (hashMap.containsKey(key + 1)){
                ret = Math.max(ret, hashMap.get(key) + hashMap.get(key + 1));
            }
        }
        return ret;
    }
}
